//////////////////////////////////////////////
// FreeListMemorySpaceWrapper.h
//
//////////////////////////////////////////////

/// Defines / Macros -------------------------

#pragma once

/// Includes ---------------------------------

// nkMemory
#include "../../Log/LogManager.h"

#include "../../Pointers/UniquePtr.h"

#include "../MemorySpaces/DefaultMemorySpace.h"
#include "../MemorySpaces/MemorySpace.h"
#include "../MemorySpaces/MemorySpaceAllocator.h"

// Standards
#include <map>

/// Internals --------------------------------

namespace nkMemory
{
	// Default value codes for invalid
	constexpr unsigned long long FREE_LIST_INVALID_SIZE = (unsigned long long)-1 ;

	// Free spot info
	struct FreeListFreeSpot
	{
		unsigned long long _size ;
	} ;
}

/// Class ------------------------------------

namespace nkMemory
{
	template <typename T, typename U>
	class FreeListMemorySpaceWrapper final
	{
		public :

			// Constructeur
			FreeListMemorySpaceWrapper (unsigned long long spaceSize, MemorySpaceAllocator<U>* spaceAllocator) noexcept
			:	_memSpace (spaceAllocator->allocate(spaceSize)),
				_freeSpots (),
				_freeSize (0)
			{
				// Ajout d'un free spot sur la totalité du space
				_addFreeSpot(0, spaceSize) ;
			}

		public :

			// Getters
			unsigned long long getFreeSize () const
			{
				return _freeSize ;
			}

		public :

			// Demande d'allocation
			unsigned long long getFittingOffsetFor (unsigned long long size, unsigned long long alignment) const
			{
				// Quick check
				if (size > _freeSize)
					return FREE_LIST_INVALID_SIZE ;

				// On retrouve un free spot compatible
				unsigned long long allocationOffset = 0 ;
				unsigned long long toAlignOffset = 0 ;
				unsigned long long alignedOffset = 0 ;

				for (const std::pair<const unsigned long long, const FreeListFreeSpot>& entry : _freeSpots)
				{
					allocationOffset = entry.first ;
					toAlignOffset = allocationOffset % alignment ;
					alignedOffset = toAlignOffset ? allocationOffset + (alignment - toAlignOffset) : allocationOffset ;

					if (alignedOffset + size - allocationOffset <= entry.second._size)
						return alignedOffset ;
				}

				return FREE_LIST_INVALID_SIZE ;
			}

			void noticeAllocation (unsigned long long offset, unsigned long long size)
			{
				// On retrouve le free spot compatible
				typename std::map<unsigned long long, FreeListFreeSpot>::const_iterator searchResult = _searchForPrecedingFreeSpot(offset) ;

				// En tout logique il ne sera pas possible de ne pas trouver à cause des interactions avec le Pager

				// Split du block donc
				// Temporaires
				unsigned long long spotOffset = searchResult->first ;
				FreeListFreeSpot spot = searchResult->second ;

				// Clear de l'entrée multi map
				_freeSpots.erase(searchResult) ;

				// Si alignement offset, alors un nouveau bloc à gauche
				unsigned long long spotInternalOffset = offset - spotOffset ;

				if (spotInternalOffset)
					_addFreeSpot(spotOffset, spotInternalOffset) ;

				// Si reste à droite maintenant
				unsigned long long totalSize = spotInternalOffset + size ;

				if (totalSize < spot._size)
					_addFreeSpot(totalSize + spotOffset, spot._size - totalSize) ;

				// Update free size
				_freeSize -= spot._size ;
			}

			void noticeFree (unsigned long long offset, unsigned long long size)
			{
				// Vide ?
				if (_freeSpots.empty())
				{
					_addFreeSpot(offset, size) ;
				}
				else
				{
					// Infos finale de nouveau bloc
					unsigned long long finalOffset = offset ;
					unsigned long long finalSize = size ;

					// Spot à gauche ?
					typename std::map<unsigned long long, FreeListFreeSpot>::const_iterator searchResult = _searchForPrecedingFreeSpot(offset) ;

					if (searchResult != _freeSpots.end())
					{
						unsigned long long spotEndingOffset = searchResult->first + searchResult->second._size ;

						// Merge ?
						if (spotEndingOffset == offset)
						{
							finalOffset = searchResult->first ;
							finalSize += searchResult->second._size ;
							_freeSize -= searchResult->second._size ;

							_freeSpots.erase(searchResult) ;
						}
					}

					// Spot à droite ?
					searchResult = _searchForFollowingFreeSpot(offset) ;

					if (searchResult != _freeSpots.end())
					{
						unsigned long long spotEndingOffset = offset + size ;

						// Merge ?
						if (spotEndingOffset == searchResult->first)
						{
							finalSize += searchResult->second._size ;
							_freeSize -= searchResult->second._size ;

							_freeSpots.erase(searchResult) ;
						}
					}

					// Et on recrée le bloc
					_addFreeSpot(finalOffset, finalSize) ;
				}
			}

		public :

			// Utilitaires
			T getOffsetPtr (unsigned long long offset) const
			{
				return _memSpace->getOffsetPtr(offset) ;
			}

		public :

			// Track spot
			inline void _addFreeSpot (unsigned long long offset, unsigned long long size)
			{
				_freeSpots.emplace(offset, FreeListFreeSpot{size}) ;
				_freeSize += size ;
			}

			// Recherche de bloc
			inline std::map<unsigned long long, FreeListFreeSpot>::const_iterator _searchForPrecedingFreeSpot (unsigned long long offset) const
			{
				std::map<unsigned long long, FreeListFreeSpot>::const_iterator searchResult = _freeSpots.lower_bound(offset) ;

				// Check bounds
				if (searchResult == _freeSpots.end() || searchResult->first > offset)
					searchResult-- ;

				return searchResult ;
			}

			inline std::map<unsigned long long, FreeListFreeSpot>::const_iterator _searchForFollowingFreeSpot (unsigned long long offset) const
			{
				std::map<unsigned long long, FreeListFreeSpot>::const_iterator searchResult = _freeSpots.upper_bound(offset) ;

				return searchResult ;
			}

		public :

			// Attributs
			UniquePtr<U> _memSpace ;

			// La map des free spots pour ce space, par offset
			std::map<unsigned long long, FreeListFreeSpot> _freeSpots ;

			// Taille restante totale dans le space
			unsigned long long _freeSize ;
	} ;
}